home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / range_tr.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  5.1 KB  |  195 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  range_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. //------------------------------------------------------------------
  18. //
  19. // d-dimensional Range Trees
  20. //
  21. // Michael Wenzel     (1990)
  22. //
  23. // Implementation  follows
  24. // Kurt Mehlhorn: Data Structures and Algorithms, Vol.3
  25. //
  26. //------------------------------------------------------------------
  27.  
  28.  
  29. #ifndef RANGETREEH
  30. #define RANGETREEH
  31.  
  32.  
  33. #include <LEDA/list.h>
  34. #include <LEDA/bb_tree.h>
  35.  
  36.  
  37. //------------------------------------------------------------------
  38. // class tuple for range trees
  39. //
  40. // Michael Wenzel          (1990)
  41. //------------------------------------------------------------------
  42.  
  43.  
  44. //------------------------------------------------------------------
  45. // class tuple
  46. //------------------------------------------------------------------
  47.  
  48. class tuple {
  49.  
  50. friend class range_tree;
  51. friend class rm_tree;
  52.  
  53.   int d;                              // dimension of tuple
  54.   int vergl_dim;                      // comparision dimension
  55.   ent* t;
  56.   ent   inf;
  57.  
  58.  
  59.  void init(int );
  60.  
  61.  
  62.  public:
  63.  
  64.  ent& operator[](int i)  { return t[i];   }
  65.  ent& info()             { return inf; }
  66.  int  dimension()        { return d; }
  67.  
  68.  int  cmp_dim()      { return vergl_dim;    }
  69.  void set_cmp(int i) { if ((1<=i) && (i<=d)) vergl_dim=i;     }
  70.  
  71.  tuple& operator=(tuple& );
  72.  
  73.  tuple();
  74.  tuple(ent,ent);
  75.  tuple(ent,ent,ent);
  76.  tuple(int );
  77.  tuple(tuple& );
  78.  ~tuple();
  79.  
  80. OPERATOR_NEW(4)
  81. OPERATOR_DEL(4)
  82.  
  83. friend ent Copy(tuple& x)   { tuple* y=new tuple(x); return Ent(y); }
  84. friend void Clear(tuple& x) { for (int i=0; i<x.d; i++)
  85.                 Clear(x.t[i]);                      }
  86.  
  87.  
  88. };
  89.  
  90. typedef tuple* tuplep;
  91. typedef tuple* range_tree_item;
  92. typedef int (*TCMP)(tuplep,tuplep);
  93.  
  94.  
  95. // ------------------------------------------------------------------
  96. //  RANGE TREE
  97. // ----------------------------------------------------------------- 
  98.  
  99. class range_tree;
  100.  
  101. typedef range_tree* range_p;
  102.  
  103. //------------------------------------------------------------------------------
  104. // rm_tree = dictionary(tuplep,range_p)  (data structure: bb-alpha tree)
  105. //------------------------------------------------------------------------------
  106.  
  107.  
  108. declare(list,range_tree_item);
  109.  
  110.  
  111. struct rm_tree : public bb_tree {
  112.  
  113.  
  114.  
  115. int              defined(tuplep y)   { return bb_tree::member(Ent(y)); }
  116. bb_tree_item     lookup(tuplep y)    { return bb_tree::lookup(Ent(y)); }
  117. bb_tree_item     ord(int y)          { return bb_tree::ord(int(y)); }
  118. void             change_inf(bb_tree_item it, range_p i) 
  119.                                      { info(it) = i; }
  120. bb_tree_item     insert(tuplep y,range_p x)
  121.                                        { return bb_tree::insert(Ent(y),Ent(x)); } 
  122. void      del(tuplep y)                { delete bb_tree::del(Ent(y)); } 
  123. void      del_item(range_tree_item it) { del(it); } 
  124. range_p&  info(bb_tree_item it)        { return (range_p&)(bb_tree::info(it)); } 
  125. range_p&  inf(bb_tree_item it)         { return (range_p&)(bb_tree::info(it)); } 
  126.  
  127. } ;
  128.  
  129.  
  130. //------------------------------------------------------------------
  131. // class range_tree
  132. //------------------------------------------------------------------
  133.  
  134. class range_tree : public rm_tree {
  135.  
  136.   friend class bb_tree;
  137.   friend class bb_node;
  138.  
  139.   int     dim;                  // dimension 
  140.  
  141.   void lrot(bb_item , bb_item);
  142.   void rrot(bb_item , bb_item);
  143.   void ldrot(bb_item , bb_item);
  144.   void rdrot(bb_item , bb_item);
  145.   bool check(tuplep , tuplep , tuplep);
  146.  
  147. virtual void copy_key(ent& x)  const { x=x; }
  148. virtual void copy_inf(ent& x)  const { x=x; }
  149. virtual void clear_key(ent& x) const { x=0; }
  150. virtual void clear_inf(ent& x) const { x=0; }
  151.  
  152. virtual int  cmp_tuple_entry(int i, tuplep x, tuplep y) 
  153. { cout << "error: virtual cmp_tuple_entry\n"; i=0; x=y=0; return 0; }
  154.  
  155. virtual range_tree* new_range_tree(int i) 
  156. { cout << "error: virtual new_range_tree\n"; i=0; return 0; }
  157.  
  158. int tuple_cmp(tuplep x, tuplep y);  
  159.  
  160. int cmp(ent& x, ent& y) { return tuple_cmp(*(tuplep*)&x,*(tuplep*)&y); }
  161.  
  162. public :
  163.  
  164.   range_tree_item insert_tuple(tuplep);
  165.   void       del(tuplep);
  166.   tuplep     del_tuple(tuplep);
  167.   void       del_item(range_tree_item it)  { del_tuple(it); } 
  168.   void       query_tuples(tuplep,tuplep,dlist&);
  169.  
  170.   int dimension()                      { return dim;                 }
  171.   int dimension(bb_tree_item x)        { return key(x)->dimension(); }
  172.  
  173.   list(range_tree_item) all_tuples();
  174.  
  175.   tuplep            key(bb_tree_item p)  { return  tuplep(p->key()); }
  176.  
  177.   range_tree_item   min(int i);
  178.   range_tree_item   max(int i);
  179.                       
  180.   void              init_iterator()    { rm_tree::init_iterator(); }
  181.   bb_tree_item      move_iterator()    { return rm_tree::move_iterator(); }
  182.  
  183.   void              clear_tuple(tuplep& );
  184.   void              clear();
  185.   void              del_tree(bb_tree_item);
  186.  
  187.   range_tree(int i)               { dim = i; } 
  188.   ~range_tree();                 
  189.  
  190.  
  191. };
  192.  
  193. #endif
  194.  
  195.